Modern processors require cache memories in order to bridge the gap between fast processors and slow main memories.
Physically and virtually indexed caches are known. In a physically indexed cache (FIG. 7), the virtual address supplied by the processor is first translated into a physical address by the Translation Lookaside Buffer (TLB). Then, the cache is addressed using this physical address.
In a virtually indexed cache (FIG. 8), the cache is directly addressed by the virtual address. A translation into the corresponding physical address only takes place in the case of a cache miss. The advantage of a virtually-indexed cache lies in the higher speed, since the translation step by the TLB is omitted. Its disadvantage shows when it comes to synonyms or aliasing.
Direct-mapped caches use a map function (as shown in FIGS. 7 and 8) to calculate a cache index from the physical address or the virtual address a and to select a line of the cache therewith. Then, a is compared to the address of the memory area (the tag of the cache entry) presently associated with this cache line. In the case of identity, there is a hit (and the cache line is used instead of the main memory), otherwise there is a miss. Mostly, (a mod cache size)/line size is used as the map function. To this end, not the complete virtual address must be stored in the cache, but a/cache size will be sufficient.
Direct-mapped caches are simpler but cause higher miss rates than n-way caches. Basically, these consist of n correspondingly smaller direct-mapped cache blocks. It is made sure that each main memory element is located in one block at most. Since the map function indicates n cache lines, the cache can contain up to n elements with map equivalent addresses. This n-fold associativity reduces the probability of clashes and increases the hit rate accordingly.
The cache type preferred at present is a virtually-indexed and real (physically) tagged cache. It is just as fast as a virtually-indexed and virtually-tagged cache, yet it avoids most of the disadvantages thereof, in particular the problems with multi-processor systems, synonyms, sharing and coherence.
It is true that a physically indexed cache is free from these disadvantages as well, but it requires a complete address translation step (virtual.fwdarw.real) by the TLB before the cache access can be initiated. On the other hand, a virtually-indexed and physically tagged cache allows for parallel TLB and cache accesses (see FIG. 9). Therefore, the instruction pipeline of the processor is shorter so that the idle time of an instruction, as a rule, decreases by one clock with the processor performance increasing accordingly.
The mechanism remains simple as long as all of the address bits (i) necessary for indexing the cache are located within the range of the address offset (address within a page). Since this address portion is not changed by the translation of the virtual address into the physical address, the cache can be addressed (indexed) thereby even before the translation step of the TLB. Only at the end of the cache access and the parallel TLB translation step is it checked, whether the physical address (the tag) associated with the cache entry is identical with the physical address supplied by the TLB. In doing so, only the most significant bits of the address that are contiguous with the index portion (i) have to be compared, since the cache entry indexed by (i) can only be associated with addresses the index bits of which have the value (i). Accordingly, only the most significant bits have to be stored in the cache as the tag (physical address).
An n-way set-associative cache of this type may only be up to n.times.2.sup.P in size, where 2.sup.P is the page size. The cache size may be increased by larger pages or increased associativity.
However, an interesting technique is page coloring. This refers to the method wherein the set-up of pages in the real memory is always such that the least significant address bits of the virtual and the physical page address are identical (see FIG. 10). Here, the virtual page number (vpn) and the cache index (i) will overlap. The overlapping portion is shown in black in FIG. 10. The corresponding part of the virtual address is called virtual color c, the part of the physical address is referred to as physical color c'. In the case of a well-colored allocation, i.e. when the virtual and physical colors match, the above mentioned limitation of the size n.times.2.sup.P is void.
If, as shown in FIG. 11, there is an additional comparison of the virtual and physical colors, the tagging (physical address) may be done without storing the corresponding color bits and only the most significant bits (r') of the physical page number have to be compared to the tag.
It is the object of the present invention to provide a cache memory device with a virtually indexed and physically tagged cache memory which allows a fast cache access even in the case of badly-colored pages. Synonyms should be admissible without alignment restrictions, however, only the access via one address (main address) has to be fast. Any access via other addresses (synonyms) can be delayed; however, it is to be secured that each of the synonymous addresses can be selected as main address, in particular the virtual color of the main address should be able to differ from the physical color.